package codingforgreat.class45;


import java.util.Arrays;
import java.util.prefs.BackingStoreException;

// 来自京东笔试
// 小明手中有n块积木，并且小明知道每块积木的重量。现在小明希望将这些积木堆起来
// 要求是任意一块积木如果想堆在另一块积木上面，那么要求：
// 1) 上面的积木重量不能小于下面的积木重量
// 2) 上面积木的重量减去下面积木的重量不能超过x
// 3) 每堆中最下面的积木没有重量要求
// 现在小明有一个机会，除了这n块积木，还可以获得k块任意重量的积木。
// 小明希望将积木堆在一起，同时希望积木堆的数量越少越好，你能帮他找到最好的方案么？
// 输入描述:
// 第一行三个整数n,k,x，1<=n<=200000，0<=x,k<=1000000000
// 第二行n个整数，表示积木的重量，任意整数范围都在[1,1000000000]
// 样例输出：
// 13 1 38
// 20 20 80 70 70 70 420 5 1 5 1 60 90
// 1 1 5 5 20 20 60 70 70 70 80 90 420 -> 只有1块魔法积木，x = 38
// 输出：2
// 解释：
// 两堆分别是
// 1 1 5 5 20 20 (50) 60 70 70 70 80 90
// 420
// 其中x是一个任意重量的积木，夹在20和60之间可以让积木继续往上搭
public class Code01_SplitBuildingBlock {
        //启发解
        public static int basic(int[] arr,int x,int i,int r){
            if (i == arr.length - 1) {
                return 1;
            }
            // i没到最后一个数
            if (arr[i + 1] - arr[i] <= x) { // 一定贴在一起
                return basic(arr, x, i + 1, r);
            } else { // 弥合！分家
                // 分家
                int p1 = 1 + basic(arr, x, i + 1, r);
                // 弥合
                int p2 = Integer.MAX_VALUE;
                int need = (arr[i + 1] - arr[i] - 1) / x;
                if (r >= need) {
                    p2 = basic(arr, x, i + 1, r - need);
                }
                return Math.min(p1, p2);
            }
        }
        public static int best(int[] arr,int x,int r){
            Arrays.sort(arr);
            int n = arr.length;
            int[] needs = new int[n];
            int size = 0;
            int spilts = 1;
            for (int i = 1; i < n; i++) {
                if(arr[i] - arr[i - 1] > x){
                    needs[size++] = arr[i] - arr[i - 1];
                    spilts++;
                }
            }
            Arrays.sort(needs,0,size);
            for(int i = 0;i < size;i++){
                int need = (needs[i] - 1) / x;
                if(r >= need){
                    r -= need;
                    spilts--;
                }else{
                    break;
                }

            }
            return spilts;
        }

    // 这是最优解
    // arr里装着所有积木的重量
    // k是魔法积木的数量，每一块魔法积木都能变成任何重量
    // x差值，后 - 前 <= x
    public static int minSplit(int[] arr, int k, int x) {
        Arrays.sort(arr);
        int n = arr.length;
        int[] needs = new int[n];
        int size = 0;
        int splits = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] - arr[i - 1] > x) {
                needs[size++] = arr[i] - arr[i - 1];
                splits++;
            }
        }
        if (splits == 1 || x == 0 || k == 0) {
            return splits;
        }
        // 试图去利用魔法积木，弥合堆！
        Arrays.sort(needs, 0, size);
        for (int i = 0; i < size; i++) {
            int need = (needs[i] - 1) / x;
            if (k >= need) {
                splits--;
                k -= need;
            } else {
                break;
            }
        }
        return splits;
    }
    // for test
        public static int[] getRadomArr (int maxSize, int maxValue,int minValue){
            int size = (int)( Math.random() * (maxSize + 1)) + 1;
            int[] res = new int[size];
            for (int i = 0; i < size; i++) {
                res[i] = (int)(Math.random() * (maxValue - minValue + 1)) + minValue;
            }
            return res;
        }
    public static void main(String[] args) {
            boolean t = true;
            for(int i = 0;i < 100;i++){
                int[] arr = getRadomArr(10,10000,1);
                int[] arr1 = arr.clone();
                int[] arr2 = arr.clone();
                int[] arr3 = arr.clone();
                int x = (int) (Math.random()*(10)) + 1;
                int k =(int) (Math.random()*(10)) + 1;
                Arrays.sort(arr1);
                int ans1 = basic(arr1,x,0,k);
                int ans2 = best(arr2,x,k);
                int ans3 = minSplit(arr3,k,x);
                if(ans1 != ans2){
                    t = false;
                    System.out.println("Oops!");
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println("V :" + ans3 );
                    break;
                }
            }
            if(t){
                System.out.println("Nice!");
            }

    }
}
